
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Stack;

public class stringlist_parser {

	char asciiTrans; // TESTING
	int intTrans; // TESTING

	// ASCII starts at 32
	final int ESCAPE_SPACE = 127;
	final int ESCAPE_BACK_SLASH = 128;
	final int ESCAPE_ASTERISK = 129;
	final int ESCAPE_PLUS = 130;
	final int ESCAPE_QUESTION = 131;
	final int ESCAPE_OR = 132;
	final int ESCAPE_LEFT_BRACKET = 133;
	final int ESCAPE_RIGHT_BRACKET = 134;
	final int ESCAPE_LEFT_PAREN = 135;
	final int ESCAPE_RIGHT_PAREN = 136;
	final int ESCAPE_PERIOD = 137;
	final int ESCAPE_SINGLE_QUOTE = 138;
	final int ESCAPE_DOUBLE_QUOTE = 139;
	final int ESCAPE_UP_ARROW = 140;
	final int ESCAPE_MINUS = 141;
	final int EPSILON = 142;
	final int IN = 143;

	boolean notFlag, clsFlag, reFlag, orFlag, charFlag, idFlag;
	boolean excludeFlag, includeFlag; // determines whether we are going to do a
										// normal include [] or an exclude [^]
	boolean excludeSet; // if true, we are on the excluding set of [^] if false
						// then we are on the set to exclude from [] or
						// charClass
	boolean insideBracket;
	int charClassNum;
	int token; // token that is being looked at
	int pos; // position in the regex string
	int currState;
	int startState; // first state in a subexpression
	int endState; // last state in a subexpression
	int lastState; // highest number state achieved
	int finalState; // last in the NFA
	int nextAsciiValue;
	String lexSpec; // regex string to be examined
	private boolean validRegex; // states whether is regex string given has
								// valid syntax
	Stack<Integer> parenStack; // keeps track of nested parentheses
	HashSet<Integer> set; // temp set
	HashSet<Integer> finishingStates; //
	HashSet<Integer> charClassValues;
	HashSet<Integer> includeValues;
	HashSet<Integer> excludeValues;
	HashSet<CharClass> characterClasses;
	HashSet<IdClass> idClasses;
	CharClass newestCharClass;
	Map<Integer, HashMap<Integer, HashSet<Integer>>> nfaMap; // NFA
	ArrayList<Integer> nfaColumns;
	IdClass newestId;
	String NFA[][]; // table to be converted into a DFA

	public stringlist_parser() {
		charClassNum = 0;
		notFlag = false;
		clsFlag = false;
		reFlag = false;
		orFlag = false;
		charFlag = true;
		idFlag = false;
		excludeFlag = false;
		includeFlag = false;
		excludeSet = false;
		insideBracket = false;
		// lexSpec = regexInput;
		pos = 0;
		currState = 1;
		lastState = 1;
		startState = 0;
		endState = 0;
		nextAsciiValue = 144;
		validRegex = true;
		nfaColumns = new ArrayList<Integer>();
		nfaColumns.add(EPSILON);
		characterClasses = new HashSet<CharClass>();
		idClasses = new HashSet<IdClass>();
		nfaMap = new HashMap<Integer, HashMap<Integer, HashSet<Integer>>>();
		nfaMap.put(1, new HashMap<Integer, HashSet<Integer>>()); // give map one
																	// state
		nfaMap.get(1).put(EPSILON, new HashSet<Integer>());
		parenStack = new Stack<Integer>();
		charClassValues = new HashSet<Integer>();

	}

	public int stringlist_peekToken(){
		char nextToken = 0;
		if (pos < lexSpec.length()) {
			nextToken = lexSpec.charAt(pos);
			if (!insideBracket) {
				while (nextToken == ' ') {
					pos++;
					if (pos >= lexSpec.length()) {
						return -1;
					}
					nextToken = lexSpec.charAt(pos);
				}
			}
		} else {
			return -1;
		}

		int retToken = nextToken;

		if (nextToken == '$') {
			String charName = "$";
			int tempPos = pos;
			boolean charFound = false;

			while (!charFound) {
				tempPos++;
				charName += lexSpec.charAt(tempPos);

				for (CharClass ch : characterClasses) {
					if (charName.equals(ch.getName())) {
						retToken = ch.getValue();
						charFound = true;
						break;
					}
				}
			}
		}

		else if (nextToken == '\\') {

			switch (lexSpec.charAt(pos + 1)) {
			case ' ':
				retToken = ESCAPE_SPACE;
				break;
			case '\\':
				retToken = ESCAPE_BACK_SLASH;
				break;
			case '*':
				retToken = ESCAPE_ASTERISK;
				break;
			case '+':
				retToken = ESCAPE_PLUS;
				break;
			case '?':
				retToken = ESCAPE_QUESTION;
				break;
			case '|':
				retToken = ESCAPE_OR;
				break;
			case '[':
				retToken = ESCAPE_LEFT_BRACKET;
				break;
			case ']':
				retToken = ESCAPE_RIGHT_BRACKET;
				break;
			case '(':
				retToken = ESCAPE_LEFT_PAREN;
				break;
			case ')':
				retToken = ESCAPE_RIGHT_PAREN;
				break;
			case '.':
				retToken = ESCAPE_PERIOD;
				break;
			case '\'':
				retToken = ESCAPE_SINGLE_QUOTE;
				break;
			case '\"':
				retToken = ESCAPE_DOUBLE_QUOTE;
				break;
			case '^':
				retToken = ESCAPE_UP_ARROW;
				break;
			case '-':
				retToken = ESCAPE_MINUS;
				break;
			}

		}

		return retToken;
	}

	public void stringlist_matchToken(int token) {
		if (token >= 144) {
			/*
			for (CharClass c : characterClasses) {
				if (c.getValue() == token) {
					pos += c.getName().length();
				}
				
			}
			*/
		} else if (token > 127) {
			pos += 2;
		} else {
			pos++;
		}

		if (reFlag && stringlist_isReChar(token)) {
			if (!nfaColumns.contains(token)) {
				nfaColumns.add(token);
			}

			// check if it is the start of subexpression
			if (startState == 0) {
				startState = currState;
			}

			// if input is not in map, add it to the start state's map
			if (!nfaMap.get(currState).containsKey(token)) {
				nfaMap.get(currState).put(token, new HashSet<Integer>());
			}

			// add end state to set
			set = nfaMap.get(currState).get(token);
			lastState++;
			set.add(lastState);
			nfaMap.get(currState).put(token, set);
			currState = lastState;

			// add currState to the map
			nfaMap.put(currState, new HashMap<Integer, HashSet<Integer>>());

			if (orFlag && pos >= lexSpec.length()) {
				if (!nfaMap.get(currState).containsKey(EPSILON)) {
					nfaMap.get(currState).put(EPSILON, new HashSet<Integer>());
				}
				set = nfaMap.get(currState).get(EPSILON);
				set.add(endState);
				nfaMap.get(currState).put(EPSILON, set);
				currState = startState;
			}
			reFlag = false; // reset flag
			if (token >= 127 && token <= 141) {
				pos++;
			}

		} else if (clsFlag && stringlist_isClsChar(token)) {
			if (includeFlag) {
				if (token == '.') {
					for (int i = 32; i < 143; i++) {
						if (stringlist_isClsChar(i) && i != '.') {
							includeValues.add(i);
						}
					}
				} else {
					includeValues.add(token);
					if (lexSpec.charAt(pos - 2) == '-' && token < 127) {
						for (int i = lexSpec.charAt(pos - 3); i <= token; i++) {
							includeValues.add(i);
						}
					}
				}
			} else if (excludeFlag) {
				if (excludeSet) {
					if (token == '.') {
						for (int i = 32; i < 143; i++) {
							if (stringlist_isClsChar(i) && i != '.') {
								excludeValues.add(i);
							}
						}
					} else {
						excludeValues.add(token);
						if (lexSpec.charAt(pos - 2) == '-' && token < 127) {
							for (int j = lexSpec.charAt(pos - 3); j <= token; j++) {
								excludeValues.add(j);
							}
						}
					}
				} else {
					if (token == '.') {
						for (int i = 32; i < 143; i++) {
							if (stringlist_isClsChar(i) && i != '.') {
								includeValues.add(i);
							}
						}
					} else {
						includeValues.add(token);
						if (lexSpec.charAt(pos - 2) == '-' && token < 127) {
							for (int k = lexSpec.charAt(pos - 3); k <= token; k++) {
								includeValues.add(k);
							}
						}
					}
				}
			}
			clsFlag = false; // reset flag
		} else if (token >= 144) {
			CharClass character = null;

			for (CharClass c : characterClasses) {
				if (c.getValue() == token) {
					character = c;
				}
			}

			if (excludeFlag && !excludeSet) {
				includeValues = character.getValidChars();
			} else if (idFlag) {
				if (!nfaColumns.contains(token)) {
					nfaColumns.add(token);
				}

				// check if it is the start of subexpression
				if (startState == 0) {
					startState = currState;
				}

				// if input is not in map, add it to the start state's map
				if (!nfaMap.get(currState).containsKey(token)) {
					nfaMap.get(currState).put(token, new HashSet<Integer>());
				}

				// add end state to set
				set = nfaMap.get(currState).get(token);
				lastState++;
				set.add(lastState);
				nfaMap.get(currState).put(token, set);
				currState = lastState;

				// add currState to the map
				nfaMap.put(currState, new HashMap<Integer, HashSet<Integer>>());

				if (orFlag && pos >= lexSpec.length()) {
					if (!nfaMap.get(currState).containsKey(EPSILON)) {
						nfaMap.get(currState).put(EPSILON,
								new HashSet<Integer>());
					}
					set = nfaMap.get(currState).get(EPSILON);
					set.add(endState);
					nfaMap.get(currState).put(EPSILON, set);
					currState = startState;
				}
			}
		} else {
			switch (token) {

			case '[':
				if (!includeFlag && !excludeFlag) {
					includeFlag = true;
				}
				includeValues = new HashSet<Integer>();
				insideBracket = true;
				break;

			case ']':
				if (includeFlag) {
					includeFlag = false;
					String name = "charClass" + charClassNum;
					newestCharClass = new CharClass(name,nextAsciiValue);
					newestCharClass.setValidChars(includeValues);
					characterClasses.add(newestCharClass);
					charClassNum++;
					nextAsciiValue++;
					idFlag = true;
					stringlist_matchToken(newestCharClass.getValue());
				} else if (excludeFlag) {
					if (excludeSet) {
						excludeSet = false;
					} else {
						for (Integer i : excludeValues) {
							if (includeValues.contains(i)) {
								includeValues.remove(i);
							}
						}
						newestCharClass.setValidChars(includeValues);
					}
				}
				insideBracket = false;
				break;

			case '^':
				includeFlag = false;
				excludeFlag = true;
				excludeSet = true;
				excludeValues = new HashSet<Integer>();
				break;

			case '(':
				parenStack.push(currState);
				startState = currState;
				if (!orFlag) {
					endState = 0;
				}
				break;

			case (int) ')':
				if (orFlag) {
					if (!nfaMap.get(currState).containsKey(EPSILON)) {
						nfaMap.get(currState).put(EPSILON,
								new HashSet<Integer>());
					}
					HashSet<Integer> set = nfaMap.get(currState).get(EPSILON);
					set.add(endState);
					nfaMap.get(currState).put(EPSILON, set);
					currState = endState;
				} else {
					if (endState == 0 && stringlist_peekToken() != '|') {
						endState = currState;
					}
				}
				parenStack.pop();
				token = stringlist_peekToken();
				if (token != '*' && token != '+') {
					if (parenStack.size() > 0) {
						startState = parenStack.peek();
					}
				}
				orFlag = false;
				break;

			case (int) '|':
				// if endState == 0, then this is the first OR in a potential
				// series
				orFlag = true;
				if (endState == 0) {
					lastState++;
					nfaMap.put(lastState,
							new HashMap<Integer, HashSet<Integer>>());
					endState = lastState;
				}
				if (!nfaMap.get(currState).containsKey(EPSILON)) {
					nfaMap.get(currState).put(EPSILON, new HashSet<Integer>());
				}
				set = nfaMap.get(currState).get(EPSILON);
				set.add(endState);
				nfaMap.get(currState).put(EPSILON, set);
				currState = startState;
				break;

			case (int) '*':
				if (endState == 0) {
					endState = currState;
				}
				if (!nfaMap.get(endState).containsKey(EPSILON)) {
					nfaMap.get(endState).put(EPSILON, new HashSet<Integer>());
				}
				set = nfaMap.get(endState).get(EPSILON);
				set.add(startState);
				nfaMap.get(endState).put(EPSILON, set);

				if (!nfaMap.get(startState).containsKey(EPSILON)) {
					nfaMap.get(startState).put(EPSILON, new HashSet<Integer>());
				}
				set = nfaMap.get(startState).get(EPSILON);
				set.add(endState);
				nfaMap.get(startState).put(EPSILON, set);
				endState = 0;
				break;

			case (int) '+':
				if (endState == 0) {
					endState = currState;
				}
				if (!nfaMap.get(endState).containsKey(EPSILON)) {
					nfaMap.get(endState).put(EPSILON, new HashSet<Integer>());
				}
				set = nfaMap.get(endState).get(EPSILON);
				set.add(startState);
				nfaMap.get(endState).put(EPSILON, set);
				endState = 0;
				break;

			}
		}
	}

	void stringlist_regExMain(String line) {
		lexSpec = line;
		includeFlag = false;
		excludeFlag = false;
		excludeSet = false;
		stringlist_regExp();
	}

	void stringlist_regExp() {
		stringlist_regExpOne();
		stringlist_regExpTail();
	}

	void stringlist_regExpTail() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '|') {
			stringlist_matchToken(token);
			stringlist_regExpOne();
			stringlist_regExpTail();
		} else {
			return; // empty string
		}
	}

	void stringlist_regExpOne() {
		stringlist_regExpTwo();
		stringlist_regExpOneTail();
	}

	void stringlist_regExpOneTail() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '(' || stringlist_isReChar(token) || token == '.' || token == '['
				|| token >= 144) {
			stringlist_regExpTwo();
			stringlist_regExpOneTail();
		} else {
			return; // empty string
		}
	}

	void stringlist_regExpTwo() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '(') {
			stringlist_matchToken(token);
			stringlist_regExp();
			token = stringlist_peekToken();
			if (token == ')') {
				stringlist_matchToken(token); // RIGHT_PAREN
			} else {
				stringlist_regExpFail();
			}
			stringlist_regExpTwoTail();
		} else if (stringlist_isReChar(token)) {
			stringlist_reChar();
			stringlist_regExpTwoTail();
		} else {
			stringlist_regExpThree();
		}
	}

	void stringlist_regExpTwoTail() {
		token = stringlist_peekToken();
		if (token == '*' || token == '+') {
			stringlist_matchToken(token);
		} else {
			return; // empty string
		}
	}

	void stringlist_regExpThree() {
		token = stringlist_peekToken();
		if (token == '.' || token == '[' || token >= 144) {
			stringlist_charClass();
		} else {
			return; // empty string
		}
	}

	void stringlist_charClass() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '.') {
			stringlist_matchToken(token);
		} else if (token == '[') {
			stringlist_matchToken(token);
			stringlist_charClassOne();
		} else {
			stringlist_definedClass();
		}
	}

	void stringlist_charClassOne() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '^') {
			stringlist_excludeSet();
		} else {
			stringlist_charSetList();
		}
	}

	void stringlist_charSetList() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (stringlist_isClsChar(token)) {
			stringlist_charSet();
			stringlist_charSetList();
		} else if (token == ']') {
			stringlist_matchToken(token);
		}
	}

	void stringlist_charSet() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (stringlist_isClsChar(token)) {
			stringlist_clsChar();
			stringlist_charSetTail();
		}
	}

	void stringlist_charSetTail() {
		if (stringlist_peekToken() == '-') {
			pos++;
			stringlist_clsChar();
		} else {
			return; // empty string
		}
	}

	void stringlist_excludeSet() {
		token = stringlist_peekToken();
		if (token == -1) {
			return; // done with this line
		}
		if (token == '^') {
			stringlist_matchToken('^');
			stringlist_charSet();
			if (stringlist_peekToken() == ']') {
				pos++;
				insideBracket = false;
				if (stringlist_peekToken() == 'I') {
					pos++;
					if (stringlist_peekToken() == 'N') {
						pos++;
						stringlist_excludeSetTail();
					}
				}
			} else {
				stringlist_regExpFail();
			}
		} else {
			stringlist_regExpFail();
		}
	}

	void stringlist_excludeSetTail() {
		if (stringlist_peekToken() == '[') {
			pos++;
			insideBracket = true;
			if (stringlist_isClsChar(stringlist_peekToken())) {
				stringlist_charSet();
			}
			if (stringlist_peekToken() == ']') {
				pos++;
				insideBracket = false;
			}
		} else {
			stringlist_definedClass();
		}
	}

	void stringlist_definedClass() {
		token = stringlist_peekToken();
		if (idFlag) {
			stringlist_matchToken(token);
		} else {
			for (CharClass c : characterClasses) {
				if (c.getValue() == token) {

					includeValues.clear();
					includeValues.addAll(c.getValidChars());
					includeValues.removeAll(excludeValues);

					newestCharClass.setValidChars(includeValues);
					pos += c.getName().length();
					break;
				}
			}
		}
	}

	void stringlist_reChar() {
		token = stringlist_peekToken();
		if (stringlist_isReChar(token)) {
			reFlag = true;
			stringlist_matchToken(token);
		} else {
			stringlist_regExpFail();
		}
	}

	boolean stringlist_isReChar(int check) {

		if (check >= 32 && check <= 142 && check != ' ' && check != '\\'
				&& check != '*' && check != '+' && check != '?' && check != '|'
				&& check != '[' && check != ']' && check != '(' && check != ')'
				&& check != '.' && check != '\'' && check != '\"'
				&& check != IN && check != ESCAPE_UP_ARROW
				&& check != ESCAPE_MINUS && check < 144) {

			return true;
		}

		else {
			return false;
		}

	}

	void stringlist_clsChar() {
		token = stringlist_peekToken();
		if (stringlist_isClsChar(token)) {
			clsFlag = true;
			stringlist_matchToken(token);
		} else {
			stringlist_regExpFail();
		}
	}

	boolean stringlist_isClsChar(int check) {
		if (check >= 32 && check <= 142 && check != '\\' && check != '^'
				&& check != '-' && check != '[' && check != ']'
				&& check != ESCAPE_SPACE && check != ESCAPE_ASTERISK
				&& check != ESCAPE_PLUS && check != ESCAPE_QUESTION
				&& check != ESCAPE_OR && check != ESCAPE_LEFT_PAREN
				&& check != ESCAPE_RIGHT_PAREN && check != ESCAPE_PERIOD
				&& check != ESCAPE_SINGLE_QUOTE && check != ESCAPE_DOUBLE_QUOTE) {
			return true;
		} else {
			return false;
		}
	}

	void stringlist_regExpFail() {
		System.out.println("Regex syntax is incorrect.");
	}

	boolean stringlist_isValid() {
		return validRegex;
	}

	public Map<Integer, HashMap<Integer, HashSet<Integer>>> stringlist_getMap() {
		return nfaMap;
	}

	void stringlist_createTable() {
		System.out.println("Done.");
	}

	CharClass stringlist_createCharClass(String line) {
		String newCharName = "";
		while (line.charAt(pos) != ' ') {
			newCharName += line.charAt(pos);
			pos++;
		}
		while (line.charAt(pos) == ' ') {
			pos++;
		}
		CharClass newestChar = new CharClass(newCharName, nextAsciiValue);
		nextAsciiValue++;
		return newestChar;
	}

	IdClass stringlist_createIdClass(String line) {
		String newIdName = "";
		while (line.charAt(pos) != ' ') {
			newIdName += line.charAt(pos);
			pos++;
		}
		while (line.charAt(pos) == ' ') {
			pos++;
		}
		// Start of a small NFA
		lastState++;
		nfaMap.put(lastState, new HashMap<Integer, HashSet<Integer>>());
		currState = lastState;
		startState = lastState;
		endState = 0;
		newestId = new IdClass(newIdName, lastState);

		// Connect to other NFAs
		HashSet<Integer> set = nfaMap.get(1).get(EPSILON);
		set.add(startState);
		nfaMap.get(1).put(EPSILON, set);
		return newestId;
	}

	void stringlist_scannerGenerator(String file) {
		try {
			FileInputStream fileStream = new FileInputStream(file);
			DataInputStream dataStream = new DataInputStream(fileStream);
			BufferedReader br = new BufferedReader(new InputStreamReader(
					dataStream));
			String fileLine;
			// Read in character classes
			while ((fileLine = br.readLine()) != null && fileLine.length() > 0) {
				
				/*
				charFlag = true;
				newestCharClass = createCharClass(fileLine);
				regExMain(fileLine);
				characterClasses.add(newestCharClass);
				pos = 0;
				/*
				 * ///---FOR TESTING----
				 * 
				 * for(CharClass c : characterClasses){
				 * System.out.print(c.getName() + "  Valid Values = ");
				 * for(Integer i : c.getValidChars()){ intTrans = i; asciiTrans
				 * = (char) intTrans; System.out.print(asciiTrans + " "); }
				 * System.out.println(); } System.out.println("\n");
				 * ////----------------
				 */
				/*
			}

			System.out.println("\nEND OF CHAR CLASS\n");
			while ((fileLine = br.readLine()) != null) {
				charFlag = false;
				idFlag = true;
				createIdClass(fileLine);
				regExMain(fileLine);
				if (endState == 0) {
					endState = currState;
				}
				newestId.addOneAcceptState(endState);
				idClasses.add(newestId);
				pos = 0;
				*/
			}
			
		} catch (FileNotFoundException e) {
			System.err.println("File not found.");
			e.printStackTrace();
		} catch (IOException e) {
			System.err.println("And I/O error has occurred");
			e.printStackTrace();
		} finally {

		}
	}
}
